package hashBuck;

// 简单实现 哈希桶
// 数组+链表

public class HashBuck {

    // 首先定义一个结点类(key-val-next)
    static class Node {
        public int key;
        public int val;
        public Node next;

        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    // 定义一个结点类型的数组
    public Node[] arr;
    // 记录当前哈希桶中有效数据的个数
    public int usedSize;
    // 给一个默认的负载因子：
    public static final float DEFAULT_LOAD_FACTOR = 0.75f; // java底层默认负载因子就是0.75

    // 构造方法进行初始化
    public HashBuck (){
        arr = new Node[2];
        this.usedSize = 0;
    }

    /** 存储key、val
     * 根据key来定位，然后检查是否有相同key，没有就进行插入usedSize++
     * @param key
     * @param val
     * @return
     */
    public void put(int key, int val) {
        // 首先新建一个结点（有了结点才能存入数组中）
        Node node = new Node(key,val);
        // key进行定位
        int index = key % arr.length;
        // 遍历、检查key:因为要考虑冲突的情况
        Node cur = arr[index];
        while(cur != null) { // cur结点不为空就说明：在所要插入的位置上已经存在了结点
            if(cur.key == key) { // 说明该位置上的节点的key值与所要插入的节点的key值一样，就进行更新val值
                //此时说明有重复:更新val值
                cur.val = val;
                return;
            }
            // 说明该位置已经有结点但不是我要存入的node结点，那就继续向当前下标位置节点的next上（也就是链表的下一个结点位置）
            cur = cur.next;
        }
        // 跳出该循环：说明此时已经走到了空的位置，就进行头插
        node.next = arr[index]; // node是此时要插入的新节点，插入到目标位置的前一个位置
        arr[index] = node;
        usedSize++; // 有效大小就++

        // 这里作图很重要，每一个数组的元素下面存的是链表（结点的next、串起来）！！！

        // 检查负载因子 大于就进行扩容：
        if(loadFac() >= DEFAULT_LOAD_FACTOR) {
            // 扩容
            grow();
        }
    }

    // 返回当前的负载因子：
    private float loadFac() {
        return usedSize * 1.0f / arr.length; // * 1.0f的目的是返回float类型
    }

    // 扩容：
    private void grow() {
        Node[] newArr = new Node[2*arr.length];
        // 遍历原数组
        for (int i = 0; i < arr.length; i++) {
            Node cur = arr[i]; // 记录当前的数组的元素对应链表的头结点
            // 遍历该链表的每一个结点 并重新进行哈希（新长度）
            while(cur != null) {
                Node curNext = cur.next; // 记录原来cur的下一个结点（很好的保证了原来数据链表的有效）
                int index = cur.key % newArr.length;
                // 然后以头插法的形式插入到新的数组
                cur.next = newArr[index]; // 表示新老数组结点的对应关系
                newArr[index] = cur; // 对新数组开始赋值结点/链表
                // cur = cur.next; // 这样就会丢失原数组的后面的链表结点
                cur = curNext; // 进行循环变化的条件
            }
        }
        // 赋值到原数组
        this.arr = newArr;
    }

    /** 通过key值来获取val值:
     *
     * @param key
     * @return
     */
    public int get(int key) {
        // 首先计算再数组的下标位置
        int index = key % arr.length;
        Node cur = arr[index];
        // 然后遍历该下标位置的链表来找有相同key值的节点来返回val值
        while (cur != null) {
            if(cur.key == key) {
                return cur.val;
            }
            // 还没有找到相同的就继续遍历该下标位置的链表
            cur = cur.next;
        }
        // 出来说明已经遍历完该位置的所有结点，没有找到
        return -1;
    }




}
